MPRI - Parisian Master of Research in Computer Science <br />Course 2.11.1: Approximation Algorithms, Randomization & Nature Programming <br />Nicolas SCHABANEL, CNRS - Université Paris Diderot <br /> <br />LECTURE 3 (2016/09/28) <br />MATHEMATICAL PROGRAMMING 2: SEMI-DEFINITE/VECTOR PROGRAMMING <br /> <br />Lecture 3: <br />[0:00:00] 0. Introduction <br />[0:02:09] 1. A quadratic program for Max-CUT <br />[0:10:17] 2. Relaxing a Quadratic Program as a Vector Program <br />[0:16:14] 3. Vector Programs = Semi-Definite Programs <br />[0:27:28] 4. VP is indeed a relaxation of integer QP <br />[0:38:43] 5. Rounding VP: the Random Hyperplane Technic <br />[1:10:09] 6. Analysis of the Random Hyperplane Algorithm <br />Exercice Session 3: <br />[1:31:47] 7. Exercise HW2-1: A Dumb Algorithm for Max-SAT <br />[1:39:12] 8. Exercise HW2-3: SDP-Approximation for Max-2SAT
